T
•
k
f : R
n
→ {1, . . . , k}
f(x)
x
f
•
x
n 2
n
•
f : R
n
→ R
•
•
•
•
•
•
x ∈ R
n
x
i
x
•
˜
x ∈ R
n
x ∈ R
n
x
˜
x
P (x |
˜
x)
•
p :
R
n
→ R p (x)
x x
P
p(x)
x
i
x
−i
p(x
i
| x
−i
)
p(x)
P
P
T
E
x
p(x)
x
y y x
p(y | x) y
x ∈ R
n
p(x) = Π
n
i=1
p(
i
|
1
, . . . ,
i−1
).
p(x) n
p(y | x)
p(x, y)
p(y | x) =
p(x, y)
y
p(x, y
)
.
X ∈ R
150×4
X
i,1
i X
i,2
i
m m
{x
(1)
, x
(2)
, . . . , x
(m)
}
x
(i)
x
(j)
X
y y
i
i
x ∈ R
n
y ∈ R
ˆy
y
ˆy = w
x
w ∈ R
n
w
i
x
i
w
x
i
w
i
ˆy
T y x
ˆy = w
x P
m
y
X
( )
y
( )
ˆ
y
( )
=
1
m
i
(
ˆ
y
( )
− y
( )
)
2
i
.
ˆ
y
( )
= y
( )
=
1
m
||
ˆ
y
( )
− y
( )
||
2
2
,
w
(X
( )
, y
( )
)
0
∇
w
= 0
⇒ ∇
w
1
m
||
ˆ
y
( )
− y
( )
||
2
2
= 0
⇒
1
m
∇
w
||X
( )
w −y
( )
||
2
2
= 0
⇒ ∇
w
(X
( )
w −y
( )
)
(X
( )
w −y
( )
) = 0
⇒ ∇
w
(w
X
( )
X
( )
w −2w
X
( )
y
( )
+ y
( )
y
( )
) = 0
⇒ 2X
( )
X
( )
w −2X
( )
y
( )
= 0
1
m
( )
||X
( )
w −y
( )
||
2
2
,
1
m
( )
||X
( )
w −y
( )
||
2
2
p(x, y)
w
ˆy = b + wx.
x
2
x
ˆy = b + w
1
x + w
2
x
2
.
Capacity
training
error
generalization
error
Error
generalization gap
optimal
capacity
Overfitting zoneUnderfitting zone
10
0
10
1
10
2
10
3
10
4
10
5
# train examples
0
1
2
3
4
5
6
Error (MSE)
Bayes error
Train (quadratic)
Test (quadratic)
Test (optimal capacity)
Train (optimal capacity)
10
0
10
1
10
2
10
3
10
4
10
5
# train examples
0
5
10
15
20
Optimal capacity (polynomial degree)
k
k k
k
k
k − 1
k − 1
k −1
bias(
ˆ
θ
m
) = E[
ˆ
θ
m
] − θ
= E
1
m
m
i=1
x
(i)
− θ
=
1
m
m
i=1
E
x
(i)
− θ
=
1
m
m
i=1
1
x
(i)
=0
x
(i)
θ
x
(i)
(1 − θ)
(1−x
(i)
)
− θ
=
1
m
m
i=1
(θ) − θ
= θ −θ = 0
bias(
ˆ
θ) = 0
ˆ
θ
{x
(1)
, . . . , x
(m)
}
x
(i)
∼ Gaussian(µ, σ
2
)
i ∈ [1, m]
p(x
(i)
; µ, σ
2
) =
1
√
2πσ
2
exp
−
1
2
(x
(i)
−µ)
2
σ
2
ˆµ
m
=
1
m
m
i=1
x
(i)
bias(ˆµ
m
) = E[ˆµ
m
] − µ
= E
1
m
m
i=1
x
(i)
− µ
=
1
m
m
i=1
E
x
(i)
− µ
=
1
m
m
i=1
µ
− µ
= µ − µ = 0
σ
2
σ
2
ˆσ
2
m
=
1
m
m
i=1
x
(i)
− ˆµ
m
2
,
ˆµ
m
bias(ˆσ
2
m
) = E[ˆσ
2
m
] − σ
2
E[ˆσ
2
m
]
E[ˆσ
2
m
] = E
1
m
m
i=1
x
(i)
− ˆµ
m
2
= E
1
m
m
i=1
(x
(i)
)
2
− 2x
(i)
ˆµ
m
+ ˆµ
2
m
=
1
m
m
i=1
E
(x
(i)
)
2
− 2E
x
(i)
1
m
m
j=1
x
(j)
+ E
1
m
m
j=1
x
(j)
1
m
m
k=1
x
(k)
=
1
m
m
i=1
1 −
2
m
E
(x
(i)
)
2
−
2
m
j=i
E
x
(i)
x
(j)
+
1
m
2
m
j=1
E
(x
(j)
)
2
+
1
m
2
m
j=1
k=j
E
x
(j)
x
(k)
=
1
m
m
i=1
(
m − 2
m
)(µ
2
+ σ
2
) −
2(m − 1)
m
(µ
2
) +
1
m
(µ
2
+ σ
2
) +
(m − 1)
m
(µ
2
)
=
m − 1
m
σ
2
ˆσ
2
m
−σ
2
/m
˜σ
2
m
=
1
m − 1
m
i=1
x
(i)
− ˆµ
m
2
E[˜σ
2
m
] = σ
2
E[˜σ
2
m
] = E
1
m − 1
m
i=1
x
(i)
− ˆµ
m
2
=
m
m − 1
E[ˆσ
2
m
]
=
m
m − 1
m − 1
m
σ
2
= σ
2
.
Var(
ˆ
θ) = E[
ˆ
θ
2
] − E[
ˆ
θ]
2
se
ˆ
θ
SE(
ˆ
θ) =
Var[
ˆ
θ].
x
1
ˆ
θ = x
1
E(
ˆ
θ
n
) = θ
ˆ
θ
n
→ θ n → ∞
m X = {x
(1)
, . . . , x
(m)
}
p (x)
p (x; θ)
θ p (x; θ) x
p (x)
θ
θ
ML
= arg max
θ
p (X; θ)
= arg max
θ
m
i=1
p (x
(i)
; θ)
arg max arg max
θ
ML
= arg max
θ
m
i=1
log p (x
(i)
; θ).
m
θ
ML
= arg max
θ
E
x∼ˆp
log p (x; θ).
{x
(1)
, . . . , x
(m)
}
θ
p(x
(1)
, . . . , x
(m)
| θ)
p(θ | x
(1)
, . . . , x
(m)
) =
p(x
(1)
, . . . , x
(m)
| θ)p(θ)
p(x
(1)
, . . . , x
(m)
)
θ
p(θ | x
(1)
, . . . , x
(m)
)
p(θ)
θ θ
m
x
(m+1)
p(x
(m+1)
| x
(1)
, . . . , x
(m)
) =
p(x
(m+1)
| θ)p(θ | x
(1)
, . . . , x
(m)
) dθ
θ
{x
(1)
, . . . , x
(m)
}
θ
θ
θ
p(θ)
p(x
(1)
, . . . , x
(m)
| θ)
Entropy( ) ≤ Entropy( )
p(w | X, y) ∝ p(y | X, w)p(w)
∝ exp
−
1
2
(y −Xw)
(y −Xw)
exp
−
1
2
(w −µ
0
)
Λ
−1
0
(w −µ
0
)
∝ exp
−
1
2
−2y
Xw + w
X
Xw + w
Λ
−1
0
w −2µ
0
Λ
−1
0
w
Λ
m
=
X
X + Λ
−1
0
−1
µ
m
= Λ
m
X
y + Λ
−1
0
µ
0
p(w | X, y) ∝ exp
−
1
2
(w −µ
m
)
Λ
−1
m
(w −µ
m
) +
1
2
µ
m
Λ
−1
m
µ
m
∝ exp
−
1
2
(w −µ
m
)
Λ
−1
m
(w −µ
m
)
.
w
µ
m
Λ
m
w
n
p(w | X
( )
, y
( )
) =
1
(2π)
n
|Λ
m
|
exp
−
1
2
(w −µ
m
)
Λ
−1
m
(w −µ
m
)
.
θ
µ
0
E[
ˆ
w
ML
] = w
Var(w
ML
) = (X
( )
X
( )
)
−1
E[
ˆ
w
MAP
] = E[Λ
m
X
( )
y
( )
]
= E
Λ
m
X
( )
X
( )
w +
= Λ
m
X
( )
X
( )
w
+ Λ
m
X
( )
E []
=
X
( )
X
( )
+ λ
−1
0
I
−1
X
( )
X
( )
w,
w
w µ
Bias(
ˆ
w
MAP
) = E[
ˆ
w
MAP
] − w
= −
λ
0
X
( )
X
( )
+ I
−1
w.
λ
0
→ ∞
λ
0
→ 0 w
Var(
ˆ
θ) = E
ˆ
θ
2
−E
ˆ
θ
2
E
ˆ
w
MAP
ˆ
w
MAP
E
ˆ
w
MAP
ˆ
w
MAP
= E
Λ
m
X
( )
ˆ
y
( )
y
( )
X
( )
Λ
m
= E
Λ
m
X
( )
X
( )
w +
X
( )
w +
X
( )
Λ
m
= Λ
m
X
( )
X
( )
ww
X
( )
X
( )
Λ
m
+ Λ
m
X
( )
E
X
( )
Λ
m
= Λ
m
X
( )
X
( )
ww
X
( )
X
( )
Λ
m
+ Λ
m
X
( )
X
( )
Λ
m
= E[
ˆ
w
MAP
]E[
ˆ
w
MAP
]
+ X
( )
X
( )
Λ
m
E
ˆ
w
MAP
ˆ
w
MAP
Var(
ˆ
w
MAP
) = E
ˆ
w
MAP
ˆ
w
MAP
− E [
ˆ
w
MAP
] E
ˆ
w
MAP
= E[
ˆ
w
MAP
]E[
ˆ
w
MAP
]
+ Λ
m
X
( )
X
( )
Λ
m
− E[
ˆ
w
MAP
]E[
ˆ
w
MAP
]
= Λ
m
X
( )
X
( )
Λ
m
=
X
( )
X
( )
+ λ
−1
0
I
−1
X
( )
X
( )
×
X
( )
X
( )
+ λ
−1
0
I
−1
w x
λ
0
Var( ˆw
ML
) =
1
m
i=1
x
2
i
> Var( ˆw
MAP
) =
λ
0
m
i=1
x
2
i
(
1+λ
0
m
i=1
x
2
i
)
2
log p(θ)
w
x + b
w
x + b = b +
m
i=1
α
i
x
x
(i)
x
(i)
α
x
φ(x) k(x, x
(i)
) = φ(x)
φ(x
(i)
)
f(x) = b +
i
α
i
k(x, x
(i)
).
φ
x
x
φ
α
k
φ
φ
x
φ(x)
x
k(x, x
(i)
) = min(x, x
(i)
)
k(u, v) = N(u −v; 0, σ
2
I)
y x k
x X y
y
c c
y
= 1 c
i
= 0
i
k
k
k
x ∈ R
100
x
1
y = x
1
x x
2
x
1
00
x
1
X
Var[x] =
1
n − 1
X
X
z = W x Var[z]
X X = UΣW
Σ
n × m X
U n×n
W m ×m
X X
Var[x] =
1
n − 1
X
X
=
1
n − 1
(UΣW
)
UΣW
=
1
n − 1
W Σ
U
UΣW
=
1
n − 1
W Σ
2
W
,
U U
U = I Σ
2
m × m
X
i Σ
2
i,i
z = W x z
Var[z] =
1
n − 1
Z
Z
=
1
n − 1
W
X
XW
=
1
n − 1
W W
Σ
2
W W
=
1
n − 1
Σ
2
X
W W
W = I X
z
X W
n × n X
X
x z
W
X y
J(w, b) = −E
x,y∼ˆp
p (y | x),
p (y | x) = N(y | x
w + b, 1)
J
J(θ) = E
x,y∼ˆp
L(x, y, θ) =
1
m
m
i=1
L(x
(i)
, y
(i)
, θ)
y L(x, y, θ) = log p(y | x; θ).
J(w, b) = λ||w||
2
2
− E
x,y∼p
p (y | x).
L
θ ← θ −
∂L(x
(i)
, y
(i)
, θ)
∂θ
i
X
J(w) = E
x∼p
||x − r(x; w)||
2
2
w
r(x) = w
wx.
k
x
x
f
∗
f
∗
(x) ≈ f
∗
(x + )
x
n
n
